| lemonoil

<center> <div style="width:90%; text-align:left"> </div> <center><h2>2720: [Violet 5]列队春游</h2><span class=green>Time Limit: </span>5 Sec  <span class=green>Memory Limit: </span>128 MB<br><span class=green>Submit: </span>215  <span class=green>Solved: </span>152<br>[<a href='submitpage.php?id=2720'>Submit</a>][<a href='problemstatus.php?id=2720'>Status</a>][<a href='bbs.php?id=2720'>Discuss</a>]</center><h2>Description</h2><div class=content><p><img height="837" width="659" alt="" src="http://www.lydsy.com/JudgeOnline/upload/201204/T1des(5).gif" /></p> <p></p></div><h2>Input</h2><div class=content><p><img height="110" width="371" alt="" src="http://www.lydsy.com/JudgeOnline/upload/201204/T1input(5).gif" /></p></div><h2>Output</h2><div class=content><p><img height="0" width="0" alt="" src="http://www.lydsy.com/JudgeOnline/upload/201204/T1output(5).gif" /><img height="81" width="640" alt="" src="http://www.lydsy.com/JudgeOnline/upload/201204/T1output(6).gif" /></p></div><h2>Sample Input</h2> </div><h2>Sample Output</h2> <h2>HINT</h2> <div class=content><p><p><img height="374" width="585" alt="" src="http://www.lydsy.com/JudgeOnline/upload/201204/T1hint(4).gif" /></p> </div><h2>Source</h2> <div class=content>

#include<bits/stdc++.h>
int i,n,s,x,c[1001]; 
double ans;
int main(){  
	scanf("%d",&n);   
    for(i=1;i<=n;i++)scanf("%d",&x),c[x]++;n++;  
    for(i=0;i<=1000;i++)  
        if(c[i])ans+=1.0*c[i]*n/(n-s),s+=c[i];  
    printf("%.2lf\n",ans);
}

考虑对i有贡献的j， j< i则共有s个， j>=i则共有n-s+1个，j必须在i中 则共有\( (n-s)! \)种排列，剩余s-1个\( P^{s-1}_n \)种排列。 =>\( \frac {CS(n-s)!P^{s-1}_n }{n!} \) = \( \frac{CS*(n-s)!n! }{n!(n-s+1)!} \) =>\( \frac{CS}{nS+1} \) 加上自己的贡献： \( \frac{CS}{ns+1}+\)=\( \frac{CS}{ns+1} + \frac{C*(ns+1)}{ns+1} \) =>\( \frac{C*(n+1)}{n-s+1} \)